package com.study.kt._01grammar._01basic

/**
 * 递归可以将复杂问题转换为一个比较简单的相同的问题
 *
 * 很多问题既可以使用递归也可以使用迭代解决，性能区别：
 *  1.当层级过多时，递归会造成栈溢出
 *  2.迭代实现起来比较麻烦
 *  3.综上可以使用尾递归优化(java没有) -->要满调用当前后没有其他操作
 */
fun main() {
    println(feibo(5))
    println(sum2(100))
}

//求第n个斐波那契 1 1 2 3 5 8 -->下一个数为前两个的和
fun feibo(n: Int): Int {
    if (n == 1) return 1
    if (n == 2) return 1
    return feibo(n - 1) + feibo(n - 2)
}

//求1..n的和 使用递归
fun sum(n: Int): Int {
    if (n == 1) return 1
    return sum(n - 1) + n
}

//使用迭代的方式
fun sum2(n: Int): Int {
    var result = 0
    var copyN: Int = n//kotlin中函数的参数无法修改
    while (copyN > 0) {
        result += copyN //此处有了+=操作所有不是尾递归
        copyN--
    }
    return result
}

//将上述方法改为尾递归操作
//使用tailrec关键字修饰方法进行尾递归优化
//优化的原理就是将递归转化为迭代实现，提高了执行效率，写起来也很简单
tailrec fun sum4(n: Int, sum: Int = 0): Int {
    if (n == 1) return n + sum
    return sum4(n - 1, sum + n)
}